package com.lzq.leetcode.lanqiao;

import java.util.*;

public class s1021 {

    public static void main(String[] args) {
        String str = "tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhf" +
                "iadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqij" +
                "gihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmad" +
                "vrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhfwl";

        int len = str.length();
        char[] cs = str.toCharArray();

        int[] dp = new int[len];

        Arrays.fill(dp, 1);

        // 遍历
        for (int i=0; i<len; i++) {
            for (int j=0; j<i; j++) {
                if (cs[j] < cs[i]) {
                    dp[i] += dp[j];
                } else if (cs[j] == cs[i]) {
                    dp[i] -= dp[j];
                }
            }
        }

        System.out.println(Arrays.stream(dp).sum());
    }
}
